' Written by Craig'n'Dave
Module Module1
    ' Binary tree using an array
    Public Class binarytree
        Private depth As Integer = 5
        Private max As Integer = 2 ^ (depth + 1) - 1
        Private btree(max) As String
        Public root = 0

        Function add(item As String)
            Dim current_node As Integer = root
            ' Find correct position
            While current_node < max AndAlso btree(current_node) <> ""
                If item < btree(current_node) Then
                    current_node = (2 * current_node) + 1
                Else
                    current_node = (2 * current_node) + 2
                End If
            End While
            ' Check overflow
            If current_node < max Then
                btree(current_node) = item
                Return True
            Else
                Return False
            End If
        End Function

        Function delete(item As String)
            ' Using Hibbard's algorithm (leftmost node of right sub-tree is the successor)   
            ' Find the node To delete
            Dim current_node As Integer = root
            While current_node < max AndAlso btree(current_node) <> item
                If item < btree(current_node) Then
                    current_node = (2 * current_node) + 1
                Else
                    current_node = (2 * current_node) + 2
                End If
            End While

            If current_node < max AndAlso btree(current_node) = item Then
                ' Handle 3 cases depending on the number Of child nodes
                Dim left_node As Integer = (2 * current_node) + 1
                Dim right_node As Integer = (2 * current_node) + 2
                If left_node < max AndAlso btree(left_node) = "" AndAlso right_node < max AndAlso btree(right_node) = "" Then
                    ' Node has no children
                    btree(current_node) = ""
                ElseIf left_node < max AndAlso btree(left_node) <> "" AndAlso right_node < max AndAlso btree(right_node) <> "" Then
                    ' Node has two children
                    ' Find the smallest value In the right Sub-tree (successor node)
                    Dim smallest As Integer = right_node
                    While (2 * smallest) + 1 < max AndAlso btree((2 * smallest) + 1) <> ""
                        smallest = (2 * smallest) + 1
                    End While
                    btree(current_node) = btree(smallest)
                    btree(smallest) = ""
                ElseIf left_node < max AndAlso btree(left_node) <> "" Then
                    ' Node has one left child
                    btree(current_node) = btree(left_node)
                    btree(left_node) = ""
                ElseIf right_node < max AndAlso btree(right_node) <> "" Then
                    ' Node has one right child
                    btree(current_node) = btree(right_node)
                    btree(right_node) = ""
                End If
                Return True
            Else
                Return False
            End If
        End Function

        Sub preorder(current_node As Integer)
            ' Visit each node: NLR
            If current_node < max AndAlso btree(current_node) <> "" Then
                Console.WriteLine(btree(current_node))
                preorder((2 * current_node) + 1)
                preorder((2 * current_node) + 2)
            End If
        End Sub

        Sub inorder(current_node As Integer)
            ' Visit each node: LNR
            If current_node < max AndAlso btree(current_node) <> "" Then
                inorder((2 * current_node) + 1)
                Console.WriteLine(btree(current_node))
                inorder((2 * current_node) + 2)
            End If
        End Sub

        Sub postorder(current_node As Integer)
            ' Visit each node: LRN
            If current_node < max AndAlso btree(current_node) <> "" Then
                postorder((2 * current_node) + 1)
                postorder((2 * current_node) + 2)
                Console.WriteLine(btree(current_node))
            End If
        End Sub

        Sub bft()
            ' Visit each node: BFT
            For current_node = 0 To max
                If btree(current_node) <> "" Then
                    Console.WriteLine(btree(current_node))
                End If
            Next
        End Sub
    End Class

    Sub main()
        Dim items() As String = {"E", "B", "G", "A", "C", "F", "H"}
        Dim binary_tree As New binarytree
        For index = 0 To items.Length - 1
            binary_tree.add(items(index))
        Next
        ' Traverse the binary tree
        Console.WriteLine("Breadth first traversal:")
        binary_tree.bft()
        Console.WriteLine("Pre-order traversal:")
        binary_tree.preorder(binary_tree.root)
        Console.WriteLine("In-order traversal:")
        binary_tree.inorder(binary_tree.root)
        Console.WriteLine("Post-order traversal:")
        binary_tree.postorder(binary_tree.root)
    End Sub

End Module
